import java.util.ArrayList;
import java.util.List;

public class BinarySearch {
    public static void main(String[] args) {
        int[] array = {1,12,84,97,152,152,367,666};
//        int result = binarySearch(array,0,array.length -1,367);
//        System.out.println(result);
        List<Integer> res = binarySearch2(array,0,array.length-1,152);
        System.out.println(res);
    }

    /**
     * 二分法查找，二分法查找必须是有序数组
     * @param array:输入数组
     * @param left:左侧索引
     * @param right:右侧索引
     * @param findVal:所需要寻找的值
     * @return 该值所在数组中的位置
     */
    public static int binarySearch(int[] array,int left, int right,int findVal){
        //如果left > right，则没有找到该值，返回-1
        if(left > right){
            return -1;
        }

        int mid = (left + right) / 2;
        int midVal = array[mid];

        if(findVal > midVal){
            return binarySearch(array,mid + 1,right,findVal);
        }else if(findVal < midVal){
            return binarySearch(array,left,mid - 1,findVal);
        }else{
            return mid;
        }
    }

    /**
     * 改进后的二分法查找，可以查找多个相同元素的位置
     * @param array:输入数组
     * @param left:左侧索引
     * @param right:右侧索引
     * @param findVal:所需要寻找的值
     * @return 该值所在数组中的位
     */
    public static ArrayList<Integer> binarySearch2(int[] array, int left, int right, int findVal){
        //如果left > right，则没有找到该值，返回-1
        if(left > right){
            return new ArrayList<>();
        }

        int mid = (left + right) / 2;
        int midVal = array[mid];

        if(findVal > midVal){
            return binarySearch2(array,mid + 1,right,findVal);
        }else if(findVal < midVal){
            return binarySearch2(array,left,mid - 1,findVal);
        }else{
            //创建一个ArrayList对象，用于存放多个相同元素的位置
            ArrayList<Integer> resIndexList = new ArrayList<Integer>();
            int temp = mid - 1;
            while(true){
                if(temp < 0 || array[temp] != findVal){
                    break;
                }
                resIndexList.add(temp);
                temp -= 1;

            }

            resIndexList.add(mid);

            temp = mid + 1;
            while(true){
                if(temp > array.length - 1 || array[temp] != findVal){
                    break;
                }
                resIndexList.add(temp);
                temp += 1;
            }
            return resIndexList;
        }
    }
}
